//最长递增子序列
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        //dp[i] 以nums[i]结尾的最长递增子序列的长度
        int n=nums.size();
        vector<int>dp(n,1);
        int res=dp[0];
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j]) dp[i]=max(dp[i],dp[j]+1);
                res=dp[i]>res?dp[i]:res;
            }
        }
        return res;
    }
};
//最长数对链
class Solution {
public:
    // static bool cmp(vector<int>& a,vector<int>& b)
    // {
    //     return a[0]<b[0];
    // }
    struct cmp
    {
        bool operator()(vector<int>& a,vector<int>& b)
        {
            return a[0]<b[0];
        }
    };
    int findLongestChain(vector<vector<int>>& pairs) 
    {
        int n=pairs.size();
        vector<int>dp(n,1);
        //sort(pairs.begin(),pairs.end(),cmp); 用静态函数的写法
        sort(pairs.begin(),pairs.end(),cmp()); //用仿函数的写法
        //dp[i] 以pairs[i]结尾的最长数对链的长度
        int res=1;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(pairs[i][0]>pairs[j][1])
                {
                    dp[i]=max(dp[i],dp[j]+1);
                    res=dp[i]>res?dp[i]:res;
                }
            }
        }
        return res;
    }
};

//最长定差子序列
class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) 
    {
        int n=arr.size();
        vector<int>dp(n,1);
        unordered_map<int,int>hash;//->数值 dp[i]
        //两层遍历会超时，所以采用哈希表做优化
        //使用哈希表就不用从0开始遍历到i-1 以找到 arr[i]-arr[j]=difference了
        //hash[nums[i]] 其实就是dp[i]
        hash[arr[0]]=1;
        int res=1;
        for(int i=1;i<n;i++)
        {
            //if(dp[i]-dp[j]==difference) dp[i]=dp[j]+1;
            //不用写成 dp[i]=max(dp[i],dp[j]+1)
            //是因为如果满足条件 一定是dp[j]+1大
            hash[arr[i]]=hash[arr[i]-difference]+1;
            res=max(res,hash[arr[i]]);
        }
        return res;
    }
};